15 Heuristics

Learning Intentions

Key knowledge

• the application of heuristics and randomised search to overcoming the soft limits of computation, including the limitations of these methods
• hill climbing on heuristic functions, the A* algorithm and the simulated annealing algorithm

Key skills

• apply heuristics methods to design algorithms to solve computationally hard problems
• explain the application of heuristics and randomised search approaches to intractable problems, including the graph colouring, 0-1 knapsack and travelling salesman problems

Dijkstra’s

procedure Dijkstra(G, s):
    dist[v] ← ∞, parent[v] ← NIL for all v
    dist[s] ← 0
    Q ← {(s,0)}
    while Q not empty:
        u ← extract_min(Q)
        for (v,w) in Adj[u]:
            if dist[u]+w < dist[v]:
                dist[v] ← dist[u]+w ; parent[v] ← u
                update(Q,v,dist[v])
    return dist, parent

A*

A* is a search algorithm to find the shortest path from a start node to a goal node.

A*

A*: f(n) = g(n) + h(n)

where:

• g(n) is actual cost
• h(n) is the heuristic cost

Run A* on the given graph. Mark the nodes explored by A*.

A*

Modify Dijkstra’s to use A*

Assume you have a list h that contains the heuristic values for each node.

e.g h[A] = 4, h[B] = 2, h[C] = 0

A*

procedure A*(G, s, t, h):
    g[v] ← ∞ ; parent[v] ← NIL for all v
    g[s] ← 0
    Q ← {(s, h(s))}                     # min-priority by f = g + h
    while Q not empty:
        u ← extract_min_f(Q)
        if u = t: break                 # stop early if goal reached
        for (v,w) in Adj[u]:
            tent ← g[u] + w
            if tent < g[v]:
                g[v] ← tent ; parent[v] ← u
                update(Q, v, g[v] + h(v))
    return g, parent                    # g[t] is shortest if h is admissible

Exercise

Q1. Consider the graph below. The source is S, the goal is G. The numbers on edges are weights, and the values in brackets are heuristic estimates h(n) from each node to the goal.

      (h=7) 
   S ——3—— A ——4—— G(h=0)
    \       |
     2      5
      \     |
       B(h=6)

At the start of A*, which node will be chosen first after S is expanded?

A. A B. B C. G D. None — the search terminates at S

Q2. A* differs from Dijkstra’s algorithm because it A. only works on unweighted graphs. B. uses a heuristic to estimate distance to the goal. C. guarantees optimality even if the heuristic overestimates. D. ignores the actual distance from the source.

Q3. If the heuristic function h(n) in A* is admissible, then A. A* is guaranteed to find an optimal path. B. A* may fail to find a path if one exists. C. A* will always expand fewer nodes than Dijkstra’s. D. A* cannot be used on weighted graphs.

Q4. Which of the following is a suitable heuristic h(n) for pathfinding in a 2D grid where movement is restricted to horizontal and vertical steps?

A. Straight-line (Euclidean) distance B. Manhattan (grid) distance C. Random values D. Weighted average of past path costs

Short Answer Style

Q5. (3 marks) Explain why A* reduces to Dijkstra’s algorithm when the heuristic function h(n) = 0 for all nodes.

Q6. (4 marks) Describe the conditions that a heuristic function must satisfy to guarantee that A* finds the shortest path. Give one example of a heuristic that satisfies these conditions in a grid navigation problem.

Q7. (5 marks) A* uses the formula f(n) = g(n) + h(n).

• Define g(n) and h(n).
• Explain the role of f(n) in selecting which node to expand.
• Give an example where a poor choice of heuristic (overestimating h) causes A* to fail.

Heuristics

• Rule of thumb: guides the search process
• Trade guaranteed optimality for speed

Why Heuristics?

• Some problems are NP-hard (e.g. TSP, Knapsack, Graph Colouring)
  
• Exact solutions are often infeasible for large input sizes
  
• Need strategies that are good enough and run in reasonable time

Properties of Heuristics

• Admissible: never overestimates cost (ensures optimality in A*)
  
• Consistent: satisfies triangle inequality (ensures finality of settled nodes)
  
• Domain-specific: often tailored to the problem
  
• Limitations: may miss optimal solution, may still be slow

Hill Climbing

An algorithmic technique that relies solely on local heuristics.

At each step, it looks at one neighbour (sometimes chosen at random).
If that neighbour has a better heuristic value (e.g. closer to the goal), move there.
If not, stay put.
Repeat until the goal is reached or you get stuck.

Hill Climbing

current = start
while current != goal:
    neighbor = select_random_neighbor(current)
    if h(neighbor) < h(current):
        current = neighbor
return current

Hill Climbing

• Imagine finding the highest peak in a hilly terrain by always moving uphill.

• Hill climbing is a metaphor, you can use other heuristics

• Example:

  • Move through a grid to some goal
  • Find the maximum x value of a function \((f(x) = -x^2 + 5x)\)

Hill Climbing in Search

Hill Climbing can be used to search through a solution space

Neighbors are similar solutions, typically differing by a small change.

Examples of Hill Climbing

Exam Timetabling

• Problem: Reduce clashes between students.
  
• Heuristic: Number of clashes in the timetable.
  
• Rule: Swap two exams if it reduces clashes.

Travelling Salesman Problem (TSP)

• Problem: Find a short tour through all cities.
  
• Heuristic: Total length of the tour.
  
• Rule: Swap two cities if it produces a shorter tour.

Knapsack Approximation

• Problem: Maximise value of items under weight capacity.
  
• Heuristic: Total value/weight ratio of the current selection.
  
• Rule: Add an item if it increases the ratio; otherwise, don’t.

Sudoku Solver

• Problem: Fill a 9×9 Sudoku grid.
  
• Heuristic: Number of rule violations (duplicate numbers in rows, columns, boxes).
  
• Rule: Change a cell only if it reduces violations.

Key Idea of Hill Climbing

• Start with a current solution.
  
• Measure it with a heuristic.
  
• Make a small local change that improves the heuristic.
  
• Stop when no further improvement is possible.

Problems

• Can get stuck in local optima.
• Can get trapped in plateaus (flat areas in the landscape).
• Outcome depends on initial conditions.
• Requires a good heuristic to guide the search.

Fixes

• Use random restarts: If stuck, restart from a different initial solution.
  • repeat ‘k’ times and pick the best result.
• Combine with Other Heuristics (Metaheuristics)
  • Use multiple heuristics or higher-level strategies to guide the search.
  • Example: simulated annealing

Variations of Hill Climbing

• Steepest-Ascent: check all neighbours, move to the best one
  

• Stochastic: pick a random neighbour, move if it improves
  

• First-Choice: scan neighbours in given order, stop at the first improvement

• All are greedy: only move if the heuristic improves

Simulated Annealing

• Adds an element of randomness
• Sometimes accepts a worse solution (probabilistically)
• Helps the search escape local maxima and explore further

Simulated Annealing

Annealing - heat treating metal to remove defects

The metaphor

• Imagine cooling a piece of metal.
• At high temperature, the atoms move freely and can “jump” to many positions.
• As the metal cools, atoms settle into a stable crystal structure (low-energy state).
• SA borrows this idea:
  • at first, the algorithm explores widely (even bad moves)
  • but as the “temperature” decreases it becomes more conservative.

Why it works

• Hill Climbing: only accepts better moves → gets stuck in local optima.
• Simulated Annealing: sometimes accepts worse moves, especially at the start (high T).
• As T lowers, it becomes more like hill climbing (only better moves).
• This balance lets it escape local optima and explore more of the solution space.

Example — Travelling Salesman Problem (TSP)

• Start with a random tour of cities.

• Swap two cities:

  • If distance decreases → accept.
  • If distance increases → accept with probability depending on T.

• Early on: lots of exploration.

• Later: fine-tuning near the best tours.

Properties

• Metaheuristic (higher-level strategy).
• Does not guarantee optimality, but often finds near-optimal solutions in large search spaces.
• Useful for NP-hard problems: TSP, timetabling, layout optimisation, etc.